function ListNode(val, next) {
    this.val = (val === undefined ? 0: val)
    this.next = (next === undefined ? null : next)
}
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 边界条件
    if (head == null || head.next == null) return head
    // 创建一个哑节点
    let newHead = new ListNode(0)
    let cur = head;
    let temp = null;
    while (cur != null) {
        temp = cur.next
        cur.next = newHead.next;
        newHead.next = cur
        cur = temp
    }
    return newHead.next
};

// 递归反转链表
/*
递归从需要反转的节点开始进行反转
* */
var reverseList = function(head) {
    // 边界条件
    if ( head == null || head.next == null) return head
    let last = reverseList(head.next)
    head.next.next = head
    head.next = null
    return last
}

let head = new ListNode(1)
let p1 = new ListNode(2)
let p2 = new ListNode(3)
let p3 = new ListNode(4)
let p4 = new ListNode(5)
head.next = p1;
p1.next = p2;
p2.next = p3;
p3.next = p4;
// console.log(head)
console.log(reverseList(head))